package lc.q101_150;

import java.util.Stack;

public class Q143 {

    public void reorderList(ListNode head) {
        // 左边链表和右边链表找出来就行
        if (head == null) {
            return;
        }
        ListNode middle = middle(head);
        ListNode l1 = head;
        ListNode l2 = middle.next;
        middle.next = null;
        // 旋转middle
        ListNode reverse = reverse(l2);
        merge(l1, reverse);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode result = left;
        while (left != null && right != null) {
            ListNode leftNext = left.next;
            ListNode rightNext = right.next;
            left.next = right;
            right.next = leftNext;
            left = leftNext;
            right = rightNext;
        }
        return result;
    }

    private ListNode reverse(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        ListNode head = null;
        ListNode next = node;
        while (next != null) {
            ListNode nextNext = next.next;
            next.next = head;
            head = next;
            next = nextNext;
        }
        return head;
    }

    private ListNode middle(ListNode head) {
        // 快慢指针
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.buildByArr(new int[]{-1,3,1,2});
        new Q143().reorderList(head);
        System.out.println(head);
    }

}
